package subject_set.top101;
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * @author haomin
 * @date 2022/10/27 19:44
 **/
public class BM1 {
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            while(head != null){
                ListNode next = head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;
                head = next;
            }
            return dummyHead.next;
        }
    }

    public class Solution2 {
        public ListNode ReverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = null;
            ListNode cur = head;
            ListNode next = cur.next;
            while(next != null){
                cur.next = pre;
                pre = cur;
                cur = next;
                next = next.next;
            }
            cur.next = pre;
            return cur;
        }
    }

    public class Solution3 {
        public ListNode ReverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newNode = ReverseList(head.next);

            second.next = head;
            head.next = null;
            return newNode;
        }
    }
}